翻訳と辞書 Words near each other ・ Damen Stan patrol vessel 4708 ・ Damen Wheeler ・ Damen-Basketball-Bundesliga ・ Damendorf ・ Damendorf Man ・ Damenlou Hotel ・ Damenwahl ・ Dameo ・ Dameon Clarke ・ Dameon Johnson ・ Dameon Porter ・ Damer ・ Damer Island ・ Damer Leslie Allen ・ Dameracherla ・ Damerau–Levenshtein distance ・ Damerdjog ・ Damerey ・ Damergidda ・ Damerham ・ Damerjog ・ Damerla Rama Rao ・ Damerlaplle ・ Damernas Värld ・ Dameron ・ Dameron (disambiguation) ・ Dameron (surname) ・ Dameron Marsh Natural Area Preserve ・ Dameron, Maryland ・ Dameron, West Virginia Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Damerau–Levenshtein distance ： ウィキペディア英語版 Damerau–Levenshtein distance In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein〔) is a distance (string metric) between two strings, i.e., finite sequence of symbols, given by counting the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters. In his seminal paper, Damerau not only distinguished these four edit operations but also stated that they correspond to more than 80% of all human misspellings. Damerau's paper considered only misspellings that could be corrected with at most one edit operation. The Damerau–Levenshtein distance differs from the classical Levenshtein distance by including transpositions among its allowable operations. The classical Levenshtein distance only allows insertion, deletion, and substitution operations. Modifying this distance by including transpositions of adjacent symbols produces a different distance measure, known as the Damerau–Levenshtein distance.〔. The isbn produces two hits: a 2007 work and a 2010 work at World Cat.〕 While the original motivation was to measure distance between human misspellings to improve applications such as spell checkers, Damerau–Levenshtein distance has also seen uses in biology to measure the variation between DNA.〔The method used in: 〕 == Definition == To express the Damerau–Levenshtein distance between two strings $a$ and $b$ a function $d\_(i,j)$ is defined, whose value is a distance between an $i$–symbol prefix (initial substring) of string $a$ and a $j$–symbol prefix of $b$. The function is defined recursively as: $\backslash qquad\; d\_(i,j)\; =\; \backslash begin$ \max(i,j) & \text \min(i,j)=0, \\ \min \begin d_(i-1,j) + 1 \\ d_(i,j-1) + 1 \\ d_(i-1,j-1) + 1_ \\ d_(i-2,j-2) + 1 \end & \text i,j > 1 \text a_i = b_ \text a_ = b_j \\ \min \begin d_(i-1,j) + 1 \\ d_(i,j-1) + 1 \\ d_(i-1,j-1) + 1_ \end & \text \end where $1\_$ is the indicator function equal to 0 when $a\_i\; =\; b\_j$ and equal to 1 otherwise. Each recursive call matches one of the cases covered by the Damerau–Levenshtein distance: * $d\_(i-1,j)\; +\; 1$ corresponds to a deletion (from a to b). * $d\_(i,j-1)\; +\; 1$ corresponds to an insertion (from a to b). * $d\_(i-1,j-1)\; +\; 1\_$ corresponds to a match or mismatch, depending on whether the respective symbols are the same. * $d\_(i-2,j-2)\; +\; 1$ corresponds to a transposition between two successive symbols. The Damerau–Levenshtein distance between and is then given by the function value for full strings: $d\_(|a|,|b|)$ where $i=|a|$ denotes the length of string and $j=|b|$ is the length of . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Damerau–Levenshtein distance」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.